/**
 * 【题】二分法查找
 * 【前提】有序数组
 * 【思想】
 *      1.将需要查找的元素和数组中间的元素比较,如果相等返回对应的数组下标，否则
 *      2.如果查找的元素比中间的元素小，则在数组的前半部分进行1步操作
 *      3.如果查找的元素比中间的元素大，则在数组的后半部分进行1步操作
 *      4.递归以上操作
 *      5.数组中不含有目标元素，返回-1
 */

const binarySearch = (target, arr, startIndex, endIndex) => {
    if (target < arr[0] || target > arr[arr.length - 1]) {
        return -1
    }
    const pointIndex = startIndex + Math.floor((endIndex - startIndex) / 2)
    if (arr[pointIndex] > target) {
       return binarySearch(target, arr, startIndex, pointIndex - 1)
    } else if (arr[pointIndex] < target) {
       return binarySearch(target, arr, pointIndex + 1, endIndex)
    } else {
        return pointIndex
    }
}

console.log(binarySearch(7, [0, 1, 2, 3, 4, 5, 6, 7,8], 0, 8))